#include <iostream>

using namespace std;
// 92. 反转链表II
// 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
// 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
// 输入：head = [1,2,3,4,5], left = 2, right = 4
// 输出：[1,4,3,2,5]

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(head == NULL || head->next == NULL || left < 1)
            return head;

        if(left == right) return head;  // 反转一个结点

        ListNode* dummyHead = new ListNode(0);  // 加上虚拟头结点
        dummyHead->next = head; // 为了操作方便，添加一个头结点
        // 初始化双指针及其他变量
        ListNode *pre = dummyHead, *p = pre->next, *q;

        int j = 1;  // 序号从1开始
        // 查找位置left的结点p及其前驱pre
        while(j < left && p != NULL) {  // 这里注意j的边界
            pre = p;
            p = p->next;
            j++;
        }
        // 将位置 left+1 到位置 right 的结点插入到pre之后
        while(j < right && p != NULL) {
            q = p->next;
            p->next = q->next;  // 删除结点q
            q->next = pre->next;    // 将结点q头插到结点pre之后
            pre->next = q;
            j++;
        }
        return dummyHead->next;
    }
};

int main() {
    int listLen = 5;
    ListNode *list = new ListNode(1);   // 创建第1个结点
    // 创建结点
    ListNode* p = list, *q;
    for(int i = 2; i <= listLen; i++) {
       q = new ListNode(i);
       p->next = q;
       p = q;
    }
    p = list;
    for(int i = 1; i <= listLen; i++) {
        cout << p->val << "->";
        p = p->next;
    }
    cout<<"NULL"<<endl;

    ListNode* newList = Solution().reverseBetween(list, 2, 4);
    p = newList;
    for(int i = 1; i <= listLen; i++) {
        cout << p->val << "->";
        p = p->next;
    }
    cout<<"NULL"<<endl;

    return 0;
}
